//
//  main.cpp
//  Prim
//
//  Created by 刘晨 on 2018/12/2.
//  Copyright © 2018 刘晨. All rights reserved.
//
/*
 
 其实思想和之前的prim算法一样，还是分为两个集合，一个是访问过的u，一个是访问过的v，找一个中间结点，判断 i到j的距离和i到temp+demp到j的距离那个短，更新就好。
 还是要维护一个距离的数组，在没有访问过的结点中每次找一个最小的边，同时也就是找到了v的结点，添加到u中，然后以这个结点为中间结点来更新距离数组，判断i到j的距离和i到temp+demp到j的距离，
 f
 */
#include <iostream>
using namespace std;
#define MAX 9999//用9999来表示不可到达。为什么不用之前的INT_MAX，因为在之后的距离的更新会产生问题。INT_MAX是int的最大值，在加就会导致胃负数，这就产生了问题
typedef struct node{
    char  data;//数据域
    int isAccess;//用来标记是否被访问过
}node;
#define VERTEXNUM 100
class Graph{
private:
    node  vertex[VERTEXNUM];//顶点表
    int edge[VERTEXNUM][VERTEXNUM];//边表
    int vertexNum;//顶点个数
    int edgeNum;//边的个数
    
    
    
    int locate(char  data);//在顶点表中找data的位置
    void initEdge();
    
public:
    Graph(int vertexNum,int edgeNum);
    void create();
    void dijkstra(char data);
    void printGraph();//输出
};

void Graph::printGraph(){
    cout<<endl;
    cout<<endl;
    cout<<"顶点边:\n";
    cout<<"vertexNum:"<<vertexNum<<" edgeNum:"<<edgeNum<<endl;
    for (int i = 0; i<vertexNum; i++) {
        cout<<vertex[i].data<<"\t";
    }
    cout<<endl;
    cout<<"边表如下：\n";
    
    for (int j = 0; j<vertexNum; j++) {
        for (int k = 0; k<vertexNum ; k++) {
            cout<<edge[j][k]<<"\t";
        }
        cout<<endl;
    }
}

int Graph::locate(char  data){
    for (int i  = 0; i<vertexNum;i++) {
        if(vertex[i].data == data){
            return i;
        }
    }
    return -1;
}
Graph::Graph(int vertexNum,int edgeNum){
    this->vertexNum = vertexNum;
    this->edgeNum = edgeNum;
    initEdge();
}
void Graph::create(){
    cout<<"input Graph data\n";
    for (int i = 0; i<vertexNum; i++) {
        cin>>vertex[i].data;
        vertex[i].isAccess = false;
    }
    char start ,end;
    int wieght = -1;
    for (int j = 0; j<edgeNum; j++) {
        
        cout<<"input start and end of edge:\n";
        cin>>start>>end>>wieght;
        int startPosition = locate(start);
        int endPosition = locate(end);
        edge[startPosition][endPosition] = wieght;
        edge[endPosition][startPosition] = wieght;
    }
    
}
void Graph:: initEdge(){
    for (int i = 0;  i<vertexNum; i++) {
        for (int j =0 ; j<=i; j++) {
            edge[i][j] = MAX;
            edge[j][i] = MAX;
        }
    }
}
void Graph::dijkstra(char data){
    int distince[100];//定义一个中间数组
    int temp = -1;//定义中间结点
    
    int position = locate(data);
    
    vertex[position].isAccess = true;
    
    //初始化distince数组
    for (int i = 0; i<vertexNum; i++) {
        if( edge[position][i] < MAX ){
            distince[i] = edge[position][i];
        }else{
            distince[i] = MAX;
        }
    }
    
   
    
    int minVertexNum = 0;//定义结点个数
    while (minVertexNum != vertexNum-1) {
        int min = MAX;
        for (int i = 0; i<vertexNum; i++) {
            if( vertex[i].isAccess == false && distince[i] < min){
                min = distince[i];
                temp = i;
            }
        }
        vertex[temp].isAccess = true;
        for (int i = 0; i<vertexNum; i++) {
            if((vertex[i].isAccess == false) && ( distince[temp]+edge[temp][i] < distince[i]) ){
                distince[i] = distince[temp]+edge[temp][i];
            }
        }
        
        
        
        
        
        minVertexNum++;
    }
    cout<<"到每个结点的最短距离如下"<<endl;
    for (int i  = 0; i<vertexNum; i++) {
        cout<<vertex[i].data<<":"<<distince[i]<<"\n";
    }
    
    
}
int main(){
    Graph a(6,8);
    a.create();
    a.printGraph();
    cout<<endl;
    a.dijkstra('1');
    return 1;
}
